翻訳と辞書 Words near each other ・ Vertical vowel system ・ Vertical wind tunnel ・ Vertical World ・ Vertical-cavity surface-emitting laser ・ Vertical-external-cavity surface-emitting-laser ・ Vertical-lift bridge ・ Verticalization ・ Vertically challenged ・ Vertically Challenged (album) ・ Vertically integrated liquid ・ Vertically scrolling video game ・ Vertically transmitted infection ・ Vertex arrangement ・ Vertex Buffer Object ・ Vertex configuration ・ Vertex cover ・ Vertex cycle cover ・ Vertex distance ・ Vertex enumeration problem ・ Vertex figure ・ Vertex function ・ Vertex Group ・ Vertex Inc ・ Vertex model ・ Vertex normal ・ Vertex of a representation ・ Vertex operator algebra ・ Vertex Pharmaceuticals ・ Vertex pipeline ・ Vertex separator Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Vertex cover ： ウィキペディア英語版 Vertex cover In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory. The minimum vertex cover problem can be formulated as a half-integral linear program whose dual linear program is the maximum matching problem. == Definition == Formally, a vertex cover $V\text{'}$ of an undirected graph $G=(V,\; E)$ is a subset of $V$ such that $\backslash forall\; uv\; \backslash in\; E\; :\; u\; \backslash in\; V\text{'}\; \backslash lor\; v\; \backslash in\; V\text{'}$, that is to say it is a set of vertices $V\text{'}$ where every edge has at least one endpoint in the vertex cover $V\text{'}$. Such a set is said to ''cover'' the edges of $G$. The following figure shows two examples of vertex covers, with some vertex cover $V\text{'}$ marked in red. :File:Vertex-cover.svg A ''minimum vertex cover'' is a vertex cover of smallest possible size. The vertex cover number $\backslash tau$ is the size of a minimum vertex cover, i.e. $\backslash tau\; =\; |V\text{'}|$. The following figure shows examples of minimum vertex covers in the previous graphs. :File:Minimum-vertex-cover.svg 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Vertex cover」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.